package opdracht4;

import java.util.ArrayList;

import opdracht4.Graph.Connection;
import opdracht4.Graph.Node;

public class Apl {

	public static final int RED = 0;
	public static final int GREEN = 1;
	public static final int WHITE = 2;
	public static final int BLUE = 3;

	public static int depth = 0;

	static Graph graph;

	public static void main(String[] args) {
		graph = new Graph();
		graph.initialize();
		System.out.println(graph.toString());
		searchCycle();
	}

	public static void searchCycle() {

		ArrayList<Connection> output = findCycle2(1, RED, graph.nodes.get(RED), new ArrayList<Connection>(),
				new ArrayList<Integer>());
		for (Connection c : output) {
			System.out.println(c.toString());
		}

		// ArrayList<Connection> cycle = findCycle(graph.nodes.get(RED), cycles,
		// graph.nodes.get(RED), usedColors, usedWeights);

		// for (Connection c: cycle) {
		// System.out.println(c.toString());
		// }

		// sample cycle
		// c[0] = graph.nodes.get(0).connections.get(4);
		// c[1] = graph.nodes.get(1).connections.get(0);
		// c[2] = graph.nodes.get(2).connections.get(3);
		// c[3] = graph.nodes.get(3).connections.get(2);

	}

	public static void print(ArrayList<Connection> c) {
		for (Connection con : c) {
			System.out.println(con.weight);
		}
	}

	@SuppressWarnings("unchecked")
	public static ArrayList<Connection> findCycle2(int depth, int rootColor, Node node, ArrayList<Connection> cycle, ArrayList<Integer> usedColors) {

		System.out.println(cycle.size());

		if (cycle.size() >= 4) {

			Connection[] cycleArray = new Connection[4];
			for (int i = 0; i < cycleArray.length; i++)
				cycleArray[i] = cycle.get(i);
			if (isCycle(cycleArray)) {
				System.out.println("done");
				return cycle;
			} else {
				System.out.println("length = 4, but no valid cycle");
				cycle.clear();
				return null;
			}
		}

		if (!usedColors.contains(rootColor)) usedColors.add(rootColor);
		
		for (Connection c : node.connections) {

			System.out.println("------------");
			for (Connection con: node.connections) {
				System.out.println(con.toString() + (c==con?"<<<<<<<<<<<<<":""));
			}
			System.out.println(":");

			Node otherNode;
			if (c.node1 == node)
				otherNode = c.node2;
			else
				otherNode = c.node1;

			boolean cont = false;
			for (Connection con : cycle)
				if (con.weight == c.weight) {
					System.out.println("Weight " + c.weight + " is already used");
					cont = true; 
					break;
				}
			if (cont) {
				continue;
			}
			
			if (usedColors.contains(otherNode.color)) {
				if (otherNode.color == rootColor && cycle.size() == 3) {
					cycle.add(c);
					return cycle;
				} else {
					System.out.println("Color " + Graph.getColor(otherNode.color) + " is already used");
					continue;
				}
			} else
				usedColors.add(otherNode.color);
			int d = depth+1;

			
			
			cycle.add(c);

			System.out.println("recursive call");

			if (cycle.size() > depth) {
				cycle.remove(cycle.size()-2);
				usedColors.clear();
			}
			
			
			
			
			ArrayList<Connection> bla = findCycle2(d, rootColor, otherNode, (ArrayList<Connection>) cycle.clone(), usedColors);
			if (bla != null)
				return bla;
			else {
				// System.out.println("continue2");
				continue;
			}

		}

		return null;

	}
	


	// // at first call root must be same as node
	// public static ArrayList<Connection> findCycle(Node root,
	// ArrayList<Connection> cycle, Node node,
	// boolean[] usedColors, boolean[] usedWeights) {
	//
	//
	// boolean done = true;
	// for (boolean b : usedColors) {
	// if (!b)
	// done = false;
	// }
	// for (boolean b : usedWeights) {
	// if (!b)
	// done = false;
	// }
	// if (node != root && cycle.size() != 4)
	// done = false;
	//
	// Connection[] checkArray = new Connection[cycle.size()];
	// for (int i = 0; i < cycle.size(); i++) {
	// checkArray[i] = cycle.get(i);
	// }
	// if (!isCycle(checkArray))
	// done = false;
	//
	// System.out.println("done = " + done);
	//
	// if (done && cycle.size() == 4)
	// return cycle;
	//
	// boolean[] usedWeightsBackup = new boolean[4];
	// for (int i = 0; i < 4; i++)
	// usedWeightsBackup[i] = usedWeights[i];
	//
	// for (Connection c : node.connections) {
	// System.out.println();
	// for (int i = 0; i < 4; i++)
	// usedWeights[i] = usedWeightsBackup[i];
	//
	// Node otherNode;
	// if (c.node1 == node)
	// otherNode = c.node2;
	// else
	// otherNode = c.node1;
	//
	// if (usedWeights[c.weight - 1]) {
	// System.out.println("weight already used: " + (c.weight - 1));
	// return null;
	// } else {
	// System.out.println("weight added: " + (c.weight - 1));
	// usedWeights[c.weight - 1] = true;
	// }
	//
	// if (usedColors[otherNode.color] ) {
	// if (otherNode == root) {
	// cycle.add(c);
	// System.out.println("DONE!");
	// return cycle;
	// }
	// System.out.println("color already used: " +
	// Graph.getColor(otherNode.color));
	// return null;
	// } else {
	// usedColors[otherNode.color] = true;
	// }
	//
	// @SuppressWarnings("unchecked")
	// ArrayList<Connection> newCycle = (ArrayList<Connection>) cycle.clone();
	// newCycle.add(c);
	// if (findCycle(root, newCycle, otherNode, usedColors, usedWeights) != null)
	// {
	// System.out.println("recursive call");
	// return findCycle(root, newCycle, otherNode, usedColors, usedWeights);
	// }
	//
	// }
	//
	// System.out.println("end reached");
	// return null;
	//
	// }

	public static boolean isCycle(Connection[] cs) {

		assert (cs.length == 4);

		boolean[] usedColorsFrom = new boolean[4];
		boolean[] usedColorsTo = new boolean[4];
		boolean[] usedWeights = new boolean[4];

		for (Connection c : cs) {
			if (usedWeights[c.weight - 1]) {
				return false;
			} else {
				usedWeights[c.weight - 1] = true;
			}

			if (usedColorsFrom[c.node1.color]) {
				if (usedColorsTo[c.node1.color]) {
					return false;
				} else {
					usedColorsTo[c.node1.color] = true;
				}
			} else {
				usedColorsFrom[c.node1.color] = true;
			}

			if (usedColorsFrom[c.node2.color]) {
				if (usedColorsTo[c.node2.color]) {
					return false;
				} else {
					usedColorsTo[c.node2.color] = true;
				}
			} else {
				usedColorsFrom[c.node2.color] = true;
			}
		}

		for (int i = 0; i < 4; i++) {
			if (usedWeights[i] == false) {
				return false;
			}
			if (usedColorsFrom[i] == false) {
				return false;
			}
			if (usedColorsTo[i] == false) {
				return false;
			}
		}

		return true;

	}

}
